package com.linyaonan.leetcode.medium._105;

import java.util.HashMap;

/**
 * @author: Lin
 * @date: 2024/9/27
 */
public class ConstructBinaryTree4 {

    HashMap<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 记录中序遍历中数值与对应索引的关系
        map.clear();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, inorder, 0, inorder.length - 1, 0);
    }

    private TreeNode build(int[] preorder, int[] inorder, int iStart, int iEnd, int pStart) {
        // 前序遍历的头结点
        int pStartValue = preorder[pStart];
        Integer iStartIndex = map.get(pStartValue);
        final TreeNode treeNode = new TreeNode(pStartValue);
        treeNode.left = build(preorder, inorder, iStart, iStartIndex - 1, pStart + 1);
        treeNode.right = build(preorder, inorder, iStartIndex + 1, iEnd, iStartIndex - iStart + pStart + 1);
        return treeNode;
    }

}
